/**
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 *
 * 你必须设计并实现时间复杂度为O(log n)的算法解决此问题。
 *
 * 链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
 */
class SearchRange {
    /**
     * 法二：将搜索左边界写成一个方法，将搜索右边界写成一个方法
     */
    public int[] searchRangeTwo(int[] nums, int target) {
        int len=nums.length;
        int a=binaryLeft(nums,0,len,target);
        int b=binaryRight(nums,0,len,target);
        return new int[]{a,b};
    }
    public int binaryLeft(int[] nums,int left,int right,int target) {
        while(left<right) {//左闭右开区间
            int mid=left+((right-left)>>>1);
            if(nums[mid]<target) {
                left=mid+1;//左闭，所以要mid+1,因为left有取到
            } else if(nums[mid]>target) {
                right=mid;//右开，所以要=mid,因为righ没有取到
            } else {
                right=mid;//缩小右边界，确定target的左边界
            }
        }
        if(left==nums.length) {//判断索引是否越界
            return -1;
        }
        return nums[left]==target?left:-1;//查看有没有这个数
    }
    public int binaryRight(int[] nums,int left,int right,int target) {
        while(left<right) {//左闭右开区间
            int mid=left+((right-left)>>>1);
            if(nums[mid]<target) {
                left=mid+1;//左闭，所以要mid+1,因为left有取到
            } else if(nums[mid]>target) {
                right=mid;//右开，所以要=mid,因为righ没有取到
            } else {
                left=mid+1;//缩小左边界，确定target的右边界
            }
        }
        if(left-1<0) {//判断索引是否越界
            return -1;
        }
        return nums[left-1]==target?left-1:-1;//查看有没有这个数
    }
    /**
     * 法一：将搜索左边界和搜索右边界合成一个办法
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int len=nums.length;
        int a=binarySearch(nums,0,len,target,true);
        int b=binarySearch(nums,0,len,target,false);
        return new int[]{a,b};
    }
    public int binarySearch(int[] nums,int left,int right,int target,boolean flag) {//flag为true时，搜索左边界，flag为false时，搜索右边界
        while(left<right) {
            int mid=left+((right-left)>>>1);
            if(nums[mid]<target) {
                left=mid+1;
            } else if(nums[mid]>target) {
                right=mid;
            } else {
                if(flag) {//寻找左边界
                    right=mid;
                } else {
                    left=mid+1;
                }
            }
        }
        if(flag) {
            // 此时 target 比所有数都大，返回 -1
            if (left == nums.length) return -1;
        // 判断一下 nums[left] 是不是 target
            return nums[left] == target ? left : -1;
        } else {
            // 判断 target 是否存在于 nums 中
        // 此时 left - 1 索引越界
        if (left - 1 < 0) return -1;
        // 判断一下 nums[left] 是不是 target
        return nums[left - 1] == target ? (left - 1) : -1;
        }
    }
}